from typing import List


class Solution:
    """
    方法：原地哈希
    通过将每个正整数放到其正确的位置（即nums[i] = i+1），然后扫描数组找到第一个不匹配的位置

    Args:
        nums: List[int] 输入的整数数组

    Returns:
        int: 第一个缺失的正整数

    Time: O(n) 每个元素最多被交换一次
    Space: O(1) 原地操作，不需要额外空间
    """
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1